Traffic on the Internet has quickly grown and continues to expand at unprecedented rates. Network switches play a critical role in sustaining that growth. Data to be passed by switches is generally divided into a series of packets that can be transmitted between devices. Packets include control information and payload data. The control information includes information used to deliver the payload data. For example, control information can include source and destination network addresses, packet sequencing identification, error detection codes, and the like. Generally, control information is found in packet headers included within the packet.
Generally, network switches have two primary planes: a control plane and a data plane. The control plane is a management plane that configures the data plane. The data plane receives packets on input ports and transmits the received packets to output ports based on the configuration. Communication between the control plane and data plane can be accomplished through a communications bus (e.g., PCIe).
Network packets can be forwarded based on longest prefix matching algorithms. The longest prefix matching algorithm is used to select an entry from a forwarding table to determine a next hop to forward incoming packets. In one technique, in order to conserve memory space, a hash table stores only a quotient, while a remainder is used as an index to the hash table, which reduces a width of table entries. However, such approaches fail to provide deterministic lookup throughput guarantees due to worst-case multiple lookups in a single memory block.